﻿using System;
using System.Reflection;

//这个题的难点在于，不可以使用贪心，因为你找到了当前最大的，可能虽然是最小的，但是满足不了条件
//比如，target=9，nums=[5,3,2]
//按照我的算法，取5，3，然后没有符合的，返回-1
//但是可以取 5，2，2，返回3
class SolBall{

    int num = 0;
    public int myBallnum2(int[] balls, int target)
    {
        Ballnum(balls, target);
      
        return num;
    }
  public void  Ballnum(int[] balls,int target)//递归法，其实没什么必要
    {

        if (target == 0) { return ; }
        int bigger = 0;
        for (int i = 0; i < balls.Length; i++) {

            
           

            if (balls[i] <= target)
            {
                if(balls[i] > bigger)
                {
                    bigger = balls[i];
                }

            }
        }
        Console.WriteLine("target   "+target+ "   bigger   " + bigger);
        if (bigger == 0)//说明没有符合条件的
        {
            num = -1;
            return ;
        }
        else{
            num++;
        Ballnum(balls, target-bigger); 
        }

       
    }
    public int myBallnum(int[] balls, int target)//迭代
    {
        //类似冒泡排序，完成两次循环
        //前提是balls是有顺序的
        Array.Sort(balls);
        int curIndex=balls.Length-1;
        int num = 0;
        while (curIndex >= 0&&target>0)
        {
            if (balls[curIndex] <= target) {
                Console.WriteLine("target   " + target + "   bigger   " + balls[curIndex]);
                target -= balls[curIndex];

                
                num++;
            }
            else
            {
                curIndex--;
            }


        }
        if(target == 0)
        {
            return num;
        }
        else
        {
            return -1;
        }


       
    }
}
class ProgramBall
{

    static void MainBall(string[] args)
    {

        //int[] balls = [1,5,2];
        //int amount = 11; 
        //int[] balls = [2];
        //int amount = 3;
        int[] balls = [5, 3, 2];
        int amount = 9;

        //string len=   Console.ReadLine();
        //   int Len=int.Parse(len);
        //   int[] balls
        //       = new int[Len];
        //   string nums = Console.ReadLine();
        //   string[] chars  = nums.Split(" ");
        //   for (int i= 0; i < chars.Length; i++){

        //       balls[i] = int.Parse(chars[i]);
        //   }

        //   string target = Console.ReadLine();
        //   int amount = int.Parse(target);

        SolBall sol = new SolBall();
       int res= sol.myBallnum2(balls, amount);
        Console.WriteLine("res" + res);

    }
}
